package com.dataStructure.Linklist;


import java.util.*;

/** 力扣：移除元素
 * 链表遍历删除：会有一个问题：就是要是考录到头节点的删除，因为删除我们都是找到满足条件的节点的前一位节点，很显然头节点的前一位
 * 是-1，找不出来的。
 * 我们通常会用   ListNode node = head;  在使用 node 遍历完之后,node是指向最后一位，head还是原来的头，因为只有第一位
 * 删不到
 */

/**
 *  链表：链表的遍历方式，如果说链表需要从头结点遍历到最后一个元素，那么就要 cur != null,
 *  如果涉及到增加删除的，则要使用 cur.next != null， 而且增加删除都是要找到目标的前一位，这是头节点处理不到，我们便可以考虑
 *  虚拟头节点
 */
public class LeetCode {


    /**
     * 排序列表
     */
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }
        list.sort((o1, o2) -> o1.val - o2.val);
        for (ListNode node : list) {
            System.out.println(node.val);
        }
        head = list.get(0);
        cur = head;
        for (int i = 1; i < list.size(); i++) {
            cur.next = list.get(i);
            cur = cur.next;
        }

        return head;
    }

    /**
     * 相交链表
     * 160
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        HashMap<ListNode, Integer> map = new HashMap<>();
        while (headA != null ) {
            map.putIfAbsent(headA, 0);
            map.put(headA, map.get(headA) + 1);
            headA = headA.next;
        }
        while ( headB != null) {
            map.putIfAbsent(headB, 0);
            map.put(headB, map.get(headB) + 1);
            if (map.get(headB) == 2) {
                return headB;
            }
            headB = headB.next;
        }

        return null;

    }

    /**
     * 合并两个链表
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null && list2 != null) {
            return list2;
        }
        if (list1 != null && list2 == null) {
            return list1;
        }
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        while (cur1 != null) {
            queue.offer(cur1);
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            queue.offer(cur2);

            cur2 = cur2.next;
        }

        ListNode head = queue.poll();
        ListNode pre = head;
        while(queue.size() != 0) {
            pre.next = queue.poll();
            pre = pre.next;
            pre.next = null;
        }
        return head;
    }

    /**
     * 链表重排
     *  借助双端队列，先将所有元素用双端队列存起来，
     *
     */
    public void reorderList(ListNode head) {
        Deque<ListNode> queue = new LinkedList<>();

        ListNode cur = head.next;
        for (; cur != null;) {
            queue.offer(cur);
            cur = cur.next;
        }
        cur = head;

        int i = 1;
        ListNode node = null;
        while (queue.size() != 0) {

            if( i %2 == 0 ) {
                node =  queue.pollFirst();
            } else {
                node = queue.pollLast();
            }

            cur.next = node;
            cur = cur.next;
            i++;
        }

        cur.next = null;
    }

    /**
     * 力扣142 环形链表|| 暴力哈希解决  待优化 双指针解法
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        HashSet<ListNode> set = new HashSet<>();
        while (cur != null) {
            if (set.contains(cur)) {
                return cur;
            } else {
                set.add(cur);
                cur = cur.next;
            }
        }
        return null;
    }

    /**
     * 链表相交 暴力哈希解决 待优化 ，双指针解法
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> listNodes = new HashSet<>();
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != null) {
            listNodes.add(curA);
            curA = curA.next;
        }
        while (curB != null) {
            if (listNodes.contains(curB)) {
                return curB;
            }
        }

        return null;

    }

    /**
     * 力扣19 删除链表的倒数第N个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dumHead = new ListNode(0,head);
        ListNode cur = dumHead;
        int i = 0;
        while(cur.next != null) {
            cur = cur.next;
            i++;
        }
        cur = dumHead;
        for (int j = 0; j < i - n;j++) {
            cur = cur.next;
        }

        cur.next = cur.next.next;
        return dumHead.next;
    }
    /**
     * 力扣 24. 两两交换链表中的节点
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dunmyHead = new ListNode(0, head);
        ListNode cur = dunmyHead;

        while (cur.next != null && cur.next.next != null) {
            ListNode temp2 = cur.next.next.next;
            ListNode temp1 = cur.next;

            cur.next = cur.next.next; //将头的下一位指向两者中的第二为
            cur.next.next = temp1; //将第二位的下一位指向第一位
            cur.next.next.next = temp2;
            //移动两位
            cur = cur.next.next;
        }
        return dunmyHead.next;
    }

    /**
     * 206. 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = head;
        //用来保存下一位
        ListNode cur = head;
        //用于遍历的
        ListNode node = head;
        for (; node != null; ) {
            cur = node.next;
            node.next = pre;
            pre = node;
            node = cur;
        }
        head.next = null;
        head = pre;
       return head;
    }



    /** 力扣：移除元素
     * 链表遍历删除：会有一个问题：就是要是考录到头节点的删除，因为删除我们都是找到满足条件的节点的前一位节点，很显然头节点的前一位
     * 是-1，找不出来的。
     * 我们通常会用   ListNode node = head;  在使用 node 遍历完之后,node是指向最后一位，head还是原来的头，因为只有第一位
     * 删不到
     */

    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode node = head;
        for (; node.next != null ;) {
            if (node.next.val == val) {
                node.next = node.next.next;
            }
            else {
                node = node.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }
}
